public class BinarySearchLeftMost {

    /**
     * 编写二分查找方法存在重复值时获取最左侧值
     *
     * @param A      : 有序数组a
     * @param target : 目标查找值
     * @return 返回索引值
     */
    public static int binarySearchLeftMost(int[] A, int target) {
        // 定义左右指针
        int i = 0, j = A.length - 1;
        // 定义结果变量索引值
        int resIndex = -1;
        // 定义循环条件
        while (i <= j) {
            // 定义中间指针m
            int m = (i + j) / 2;
            // 判断A[m] 值 与 target值
            if (target < A[m]) {
                // 中间值大 : 指针[m , j]中的值都会比target值大
                j = m - 1;
            } else if (A[m] < target) {
                // 中间值小 : 指针[i , m]中的值都会比target值小
                i = m + 1;
            } else {
                // A[m] == target: 将结果存储到结果索引值中, 并将右侧边界缩小,继续进行程序,直到程序结束,获取最左侧结果
                resIndex = m;
                j = m - 1;
            }
        }
        //i > j : 结束循环 , 返回结果索引值
        return resIndex;
    }

    /**
     * 编写二分查找方法存在重复值时获取最左侧值,修改返回值
     *
     * @param A      : 有序数组a
     * @param target : 目标查找值
     * @return 返回 >= target最靠左的索引位置
     */
    public static int binarySearchLeftMost1(int[] A, int target) {
        // 定义左右指针
        int i = 0, j = A.length - 1;
        // 定义循环条件
        while (i <= j) {
            // 定义中间指针m
            int m = (i + j) / 2;
            // 判断A[m] 值 与 target值
            if (target <= A[m]) {
                // 中间值>= target
                j = m - 1;
            } else {
                // 中间值小 : 指针[i , m]中的值都会比target值小
                i = m + 1;
            }
        }
        //返回 >= target最靠左的索引位置
        return i;
    }

    /**
     * 编写二分查找方法存在重复值时获取最右侧值,返回值
     *
     * @param A      : 有序数组a
     * @param target : 目标查找值
     * @return 返回  <= 索引值 最靠右的索引值结果
     */
    public static int binarySearchRightMost1(int[] A, int target) {
        // 定义左右指针
        int i = 0, j = A.length - 1;
        // 定义循环条件
        while (i <= j) {
            // 定义中间指针m
            int m = (i + j) / 2;
            // 判断A[m] 值 与 target值
            if (target < A[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        //返回  <= 索引值 最靠右的索引值结果
        return i - 1;
    }
}
